package com.wj.algorithm.lintcode;

public class P114 {
    public int uniquePaths(int m, int n) {
        if(m < 1 || n < 1) {
            return 0;
        }
        if(m == 1 || n == 1) {
            return 1;
        }
        
        int[] temp = new int[n];
        for(int i = 0; i < m; i ++) {
            for(int j = 0; j < n; j ++) {
                if(i == 0 || j == 0) {
                    temp[j] = 1;
                } else {
                    temp[j] = temp[j - 1] + temp[j];
                }
            }
        }
        
        return temp[n - 1];
    }
    
    public static void main(String[] args) {
        System.out.println(new P114().uniquePaths(3, 7));
    }
}
